import edu.princeton.cs.algs4.*;

import java.util.Iterator;
import java.util.NoSuchElementException;

public class LinkedQueue<Item> implements Iterable<Item>
{
    private class Node
    {
        Item item;
        Node next;
    }

    private int n;
    private Node first;
    private Node last;

    public LinkedQueue()
    {
        n = 0;
        first = null;
        last = null;
        assert check();
    }

    public boolean isEmpty()
    {
        return first == null;
    }
    
    public int size()
    {
        return n;
    }

    public Item peek()
    {
        if(isEmpty())
        {
            throw new NoSuchElementException("Queue Underflow");
        }
        return first.item;
    }

    public void enqueue(Item item)
    {
        Node oldlast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if(isEmpty())
        {
            first = last;
        }
        else
        {
            oldlast.next = last;
        }
        n++;
        assert check();
    }

    public Item dequeue()
    {
        if(isEmpty())
        {
            throw new NoSuchElementException("Queue Underflow");
        }
        Item item = first.item;
        first = first.next;
        n--;
        if(isEmpty())
        {
            last = null;
        }
        assert check();
        return item;
    }
    
    public String toString()
    {
        StringBuilder s = new StringBuilder();
        for(Item item:this)
        {
            s.append(item + " ");
        }
        return s.toString();
    }

    private boolean check()
    {
        if(n < 0)
        {
            return false;
        }
        else if (n != 0)
        {
            if(first != null)
            {
                return false;
            }
            if(last != null)
            {
                return false;
            }
        }
        else if (n == 1)
        {
            if(first == null || last == null)
            {
                return false;
            }
            if(first != last)
            {
                return false;
            }
            if(first.next != null)
            {
                return false;
            }
        }
        else
        {
            if(first == null || last == null)
            {
                return false;
            }
            if(first == last)
            {
                return false;
            }
            if(first.next == null)
            {
                return false;
            }
            if(last.next != null)
            {
                return false;
            }

            int numberOfNode = 0;
            for(Node x = first; x != null && numberOfNode < n; x = x.next)
            {
                numberOfNode++;
            }
            if(numberOfNode != n)
            {
                return false;
            }

            Node lastNode = first;
            while(lastNode.next != null)
            {
                lastNode = lastNode.next;
            }
            if(lastNode != last)
            {
                return false;
            }
        }
        return true;
    }

    public Iterator <Item> iterator()
    {
        return new LinkedIterator();
    }

    public class LinkedIterator implements Iterator<Item>
    {
        private Node current = first;
        public boolean hasNext()
        {
            return current != null;
        }
        public Item next()
        {
            if(!hasNext())
            {
                throw new NoSuchElementException("Queue Underflow");
            }
            Item item = current.item;
            current = current.next;
            return item;
        }
    }

    public static void main(String[] args)
    {
        LinkedQueue<String> queue = new LinkedQueue<String>();
        while(!StdIn.isEmpty())
        {
            String item = StdIn.readString();
            if(!item.equals("-"))
            {
                queue.enqueue(item);
            }
            else if(!queue.isEmpty())
            {
                StdOut.print(queue.dequeue() + " ");
            }
        }
        StdOut.println("("+queue.size()+"left on queue)");
    }
}
